# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2023/1/7 18:34
@FileName      : 弗洛伊德算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
"""
通过将所有的顶点分别作为“中间顶点”，最终得到的表就记录了各个顶点之间的最短路径
"""
V = 4  # 顶点的个数
INF = float('inf')  # 设定一个最大值
P = [[0] * V for i in range(V)]  # 记录各个顶点之间的最短路径
# 有向加权图中各个顶点之间的路径信息
graph = [[0, 3, INF, 5],
         [2, 0, INF, 4],
         [INF, 1, 0, INF],
         [INF, INF, 2, 0]]


def floydWarshall(graph):
    for n in range(V):
        for i in range(V):
            for j in range(V):
                if i >= j:
                    continue
                path_weight = graph[i][n] + graph[n][j]
                if path_weight < graph[i][j]:
                    graph[i][j] = path_weight
                    # 记录此路径
                    P[i][j] = n


floydWarshall(graph)
print(graph)
print(P)


def print_path(p1, p2):
    mp = P[p1][p2]
    if mp == 0:
        print('-%d' % (p2 + 1), end='')
    else:
        print_path(p1, mp)
        print_path(mp, p2)


for i in range(V):
    for j in range(V):
        if i >= j:
            continue
        print('%d-%d的最短路径为：' % (i + 1, j + 1), end='')
        print(i + 1, end='')
        print_path(i, j)
        print(',权值为%d' % (graph[i][j]))
